package leetcode.D2000.T1011;

class Solution {
//    public int shipWithinDays(int[] weights, int D) {
//        int sum = 0, maxWeight = Integer.MIN_VALUE;
//        for(int i=0; i<weights.length; ++i) {
//            sum += weights[i];
//            maxWeight = Math.max(maxWeight, weights[i]);
//        }
//        int left = maxWeight, right = sum;
//        while(left < right) {
//            int mid = left + (right-left) / 2;
//            int time = getTime(weights, mid);
//            if(time <= D) {
//                right = mid;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return left;
//    }
//    private int getTime(int[] weights, int carry) {
//        int time = 0, current = 0;
//        for(int i=0; i<weights.length; ++i) {
//            if(current + weights[i] <= carry) {
//                current += weights[i];
//            } else {
//                time++;
//                current = weights[i];
//            }
//        }
//        return time+1;
//    }

    // 二刷
    /*public int shipWithinDays(int[] weights, int D) {
        int maxWeight = weights[0];
        for(int i=1; i<weights.length; ++i) {
            maxWeight = Integer.max(maxWeight, weights[i]);
            weights[i] += weights[i-1];
        }
        int left = maxWeight, right = weights[weights.length-1];
        while(left < right) {
            int mid = left + (right - left) / 2;
            int time = getTime(weights, mid);
            if(time > D) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int getTime(int[] weights, int k) {
        int time = 0, i = 0;
        while(i < weights.length) {
            int j = i;
            while(j < weights.length) {
                int carry = i > 0 ? weights[j] - weights[i-1] : weights[j];
                if(carry > k) {
                    --j;
                    break;
                }
                ++j;
            }
            i = j + 1;
            time++;
        }
        return time;
    }*/

    // 三刷
    public int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int i = 0; i < weights.length; i++) {
            right += weights[i];
            left = Math.max(weights[i], left);
        }
        while(left < right) {
            int mid = left + (right - left) / 2;
            if (canSuccess(weights, mid, D)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canSuccess(int[] weights, int capacity, int D) {
        int totalDay = 1, i = 0, remain = capacity;
        while (i < weights.length) {
            if (remain >= weights[i]) {
                remain -= weights[i];
                ++i;
            } else {
                remain = capacity;
                totalDay++;
            }
        }
        return totalDay <= D;
    }
}